Fast Parallel Algorithms for Submodular p-Superseparable Maximization

Abstract

Maximizing a non-negative, monontone, submodular function over elements under a cardinality constraint (SMCC) is a well-studied NP-hard problem. It has important applications in, e.g., machine learning and influence maximization. Though the theoretical problem admits polynomial-time approximation algorithms, solving it in practice often involves frequently querying submodular functions that are expensive to compute. This has motivated significant research into designing parallel approximation algorithms in the adaptive complexity model; adaptive complexity (adaptivity) measures the number of sequential rounds of function queries an algorithm requires. The state-of-the-art algorithms can achi..